<?php
	session_start();
	
	// PROSES UNTUK RESET
	if(isset($_GET['reset']))
	{
		session_destroy();
        echo "<meta http-equiv=\"refresh\" content=\"0;url='index.php'\" />";
	}
	
	// PROSES UNTUK FORM I
	if(isset($_POST['config_awal']))
	{
		$_SESSION['konfigurasi_knapsack'] = array("kuota" => $_POST['kuota_knapsack'] , "jumlah_jenis" => $_POST['jumlah_jenis']);
	}
	
	// PROSES UNTUK FORM II
	if(isset($_POST['config_barang']))
	{
		$barang = array();
		for($counter=1;$counter <= $_SESSION['konfigurasi_knapsack']['jumlah_jenis'];$counter++)
		{
			$berat = 'berat_' . $counter;
			$nilai = 'nilai_' . $counter;
			array_push($barang,array("nomor" => $counter , "berat" => $_POST[$berat] , "nilai" => $_POST[$nilai]));
		}
		$_SESSION['barang'] = $barang;
		
		// SETTING SOLUSI LANGKAH 0
/*		$solusi = array();
		for($counter=0;$counter <= $_SESSION['konfigurasi_knapsack']['kuota'];$counter++)
		{
			array_push($solusi,array("f(0)" => 0));
		}
		$_SESSION['solusi'] = array($solusi);
*/	}
		
	// PROSES PENGHITUNGAN KNAPSACK TIAP STEP
	function dynamicProgramming($step)
	{
		$solusi = array();
		
		if($step == 0)
		{
			for($counter=0;$counter <= $_SESSION['konfigurasi_knapsack']['kuota'];$counter++)
			{
				array_push($solusi,0);
			}
		}
		
		else
		{
			// PERSIAPAN LIST BARANG YANG DIPAKAI DI STEP INI
			$barang = array();
			for($counter = 0; $counter < $step; $counter++)
			{
				array_push($barang,$_SESSION['barang'][$counter]);
			}
			
			$last_solution = $_SESSION['solusi'][$step-1];

			// PROSES PENGERJAAN
			$solusi = array();
			for($counter=0;$counter <= $_SESSION['konfigurasi_knapsack']['kuota'];$counter++)
			{				
				// INDEX POSISI LAST_SOLUTION UNTUK BARANG KE-X
				$index = $counter - ($barang[$step-1]['berat']);

				// JIKA ADA NILAI f i-1 (y-wi)
				if(isset($last_solution[$index]))
				{
					$new_solution = max($last_solution[$index]+$barang[$step-1]['nilai'],$last_solution[$counter]);
				}
				else
				{
					$new_solution = ($last_solution[$counter]);
				}
				
				array_push($solusi,$new_solution);
			}
		
		
		}

			if(isset($_SESSION['solusi']))
				$temp_solusi = $_SESSION['solusi'];
			else
				$temp_solusi = array();
				
			array_push($temp_solusi,$solusi);
			$_SESSION['solusi'] = $temp_solusi;		
			$posisi = $step-1 ;

		
		if($step>0)
		{	// PENAMPILAN HASIL
			echo "<br>Kapasitas Knapsack : " . $_SESSION['konfigurasi_knapsack']['kuota'] . "<br><br>";

			for($counter = 0 ; $counter < $_SESSION['konfigurasi_knapsack']['jumlah_jenis'] ; $counter++)
			{
				echo "Barang ke : " . ($counter+1) . "<br>";
				echo "   Berat : " . $_SESSION['barang'][$counter]['berat'] . "<br>";
				echo "   Nilai : " . $_SESSION['barang'][$counter]['nilai'] . "<br><br>";
			}
			
			echo "<h2> STEP $step </h2>";
			echo "<table border = 1>";
			echo "<tr>";
				echo "<td rowspan=2> y </td>";
				echo "<td colspan=2> </td>";
				echo "<td colspan=2> SOLUSI OPTIMUM </td>";
			echo "</tr>";
			echo "<tr>";
				echo "<td> f$posisi(y) </td>";
				echo "<td>" . $barang[$step-1]['nilai'] . " + f$posisi(y-" . $barang[$step-1]['berat'] . ")</td>";
				echo "<td> f$step(y) </td>";
				echo "<td> BARANG </td>";
			echo "</tr>";
			
			$counter = 0;

				for($counter=0;$counter <= $_SESSION['konfigurasi_knapsack']['kuota'];$counter++)
				{				
					// INDEX POSISI LAST_SOLUTION UNTUK BARANG KE-X
					$index = $counter - ($barang[$step-1]['berat']);

				echo "<tr>";
					echo "<td> $counter </td>";
					echo "<td>" . $_SESSION['solusi'][$step-1][$counter] . "</td>";

				// JIKA ADA NILAI f i-1 (y-wi)
					if(isset($last_solution[$index]))
					{
						$value = $last_solution[$index]+$barang[$step-1]['nilai'];
						echo "<td>$value</td>";
					}
					else
					{
						echo "<td> - ~ </td>";
					}

					echo "<td>" . $_SESSION['solusi'][$step][$counter] . "</td>";
					echo "<td> BARANG </td>";
					echo "</tr>";
				}
			echo "</table>";
			echo "<br>";
				$posisi = $_SESSION['konfigurasi_knapsack']['kuota'];
			echo "Jadi Keuntungan Maksimum pada step ini adalah : " . $_SESSION['solusi'][$step][$posisi] . "<br><br>";
		}
	}

//============================================================================================================================
//============================================================================================================================
//============================================================================================================================
	
	// PROGRAM UTAMA
	if(!isset($_SESSION['konfigurasi_knapsack']) && !isset($_SESSION['barang']))
	{
		// FORM I INPUT BATAS KNAPSACK DAN TOTAL JENIS BARANG
		echo " <form action=index.php method=post>";
		echo "	Kapasitas Knapsack : <input type=text name=kuota_knapsack> <br>";
		echo "	Jumlah Variasi Barang : <input type=text name=jumlah_jenis><br>";
		echo "	<input type=submit name=config_awal value=Next>";
		echo "</form>";
	}

	else if(isset($_SESSION['konfigurasi_knapsack']) && !isset($_SESSION['barang']))
	{
		// FORM II INPUT DAFTAR BARANG
		echo "Total Kapasitas Knapsack : " . $_SESSION['konfigurasi_knapsack']['kuota'] . "<br><br>";
		
		echo " <form action=index.php method=post>";
		
		for($counter=1;$counter <= $_SESSION['konfigurasi_knapsack']['jumlah_jenis'];$counter++)
		{
			echo " Barang ke $counter <br>";
			echo "	Berat Barang : <input type=text name=berat_$counter> <br>";
			echo "	Nilai Barang : <input type=text name=nilai_$counter><br><br>";
		}
		
		echo "	<input type=submit name=config_barang value=\"Mulai Hitung\">";
		echo "</form>";
	}
	
	else if(isset($_SESSION['konfigurasi_knapsack']) && isset($_SESSION['barang']))
	{
		echo "<a href=?reset=1> <button> RESET </button></a>";
		
		// DI SINI PROSES PENGERJAAN ALGORITMANYA
		for($step=0 ; $step <= $_SESSION['konfigurasi_knapsack']['jumlah_jenis'] ; $step++)
			dynamicProgramming($step);
	}
	?>